package main

func main() {

}

type road struct {
	dst   int
	price int
}

//#link: https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/
func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
	const inf = 10000*101 + 1
	//f[t][i] 表示t次航班到达i的最小花费
	f := make([][]int, k+2)
	for i := range f {
		//可能到达n个站点
		f[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = inf
		}
	}
	//0次航班到达src的花费为0
	f[0][src] = 0
	for t := 1; t <= k+1; t++ {
		for _, flight := range flights {
			j, i, cost := flight[0], flight[1], flight[2]
			//前 t-1 次航班的最小花费为 f[t-1][j] 加上最后一次航班的花费 cost(j,i) 中的最小值
			f[t][i] = min(f[t][i], f[t-1][j]+cost)
		}
	}
	ans := inf
	for t := 1; t <= k+1; t++ {
		ans = min(ans, f[t][dst])
	}
	if ans == inf {
		ans = -1
	}
	return ans
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
